package DataStructure.arrayAndList.arrayApply;


/**
 * @author liujun
 * @version 1.0
 * @date 2018-8-8 下午07:03:55
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @description 41. 缺失的第一个正数
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 */
public class FirstLostPositiveNum {

    public int GetAnswer(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        // 整理负数
        for (int i = 0; i < array.length; i++) {
            // tips:需要考虑0
            if (array[i] <= 0) {
                array[i] = array.length + 1;
            }
        }
        // 转换负数
        for (int i = 0; i < array.length; i++) {
            int num = Math.abs(array[i]);
            if (num <= array.length) {
                // tips:num - 1
                array[num - 1] = -Math.abs(array[num - 1]);
            }
        }
        // 计算结果
        for (int i = 0; i < array.length; i++) {
            if (array[i] > 0) {
                return i + 1;
            }
        }
        return array.length;
    }
}
